#include<iostream>
#include<string.h>
using namespace std;
#define MAXSIZE 100

typedef struct
{
	int weight;
	int parent, lchild, rchild; 
}HTNode, * HuffmanTree;

typedef char** HuffmanCode; 
void Select(HuffmanTree HT, int t, int &s1, int &s2)
{		
	for (int i = 1; i <= t; i++) 
	{
		if (HT[i].parent == 0) 
		{
			s1 = s2 = i;
			break;
		}
	}
	int temp; 
	for (int i = 1; i <= t; i++) 
		if (HT[i].parent == 0) 
		{
			if (s1 == s2) 
				if (HT[i].weight < HT[s1].weight) 
					s1 = i;
				else
					s2 = i;
			else if (HT[i].weight < HT[s1].weight && HT[i].weight < HT[s2].weight)
			{
				s2 = s1;
				s1 = i;
			}
			else if (HT[i].weight > HT[s1].weight && HT[i].weight < HT[s2].weight)
				s2 = i; 
		}
}

void HT_OutPut(HuffmanTree HT, int n) 
{
	cout << ">> 该哈夫曼树的存储结构如下:" << endl;
	cout << "\t结点\t权重\t父亲\t左孩子\t右孩子" << endl;
	for (int i = 1; i < 2*n; i++)
		cout << "\t  "
		<< i
		<< "\t  "
		<< HT[i].weight
		<< "\t  "
		<< HT[i].parent
		<< "\t    "
		<< HT[i].lchild
		<< "\t    "
		<< HT[i].rchild
		<< endl;
}

void CreateHuffmanTree(HuffmanTree &HT, int n) 
{
	if (n <= 1)
		return;
	int m = 2 * n - 1; 
	HT = new HTNode[m + 1]; 
	for (int i = 0; i <= m; i++)
	{
		HT[i].weight = 0;
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	cout << "依次输入叶子结点的权值: ";
	for (int i = 1; i <= n; i++) 
		cin >> HT[i].weight;
	getchar();
	for (int i = n + 1; i <= m; i++)
	{
		int s1, s2; 
		Select(HT, i - 1, s1, s2); 

		HT[s1].parent = i;
		HT[s2].parent = i;
	
		HT[i].lchild = s1;
		HT[i].rchild = s2;

		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
	HC = new char* [n + 1]; 
	char* cd = new char[n]; 
	cd[n - 1] = '\0';
	for (int i = 1; i <= n; i++) 
	{
		int start = n - 1; 
		int c = i;
		int f = HT[i].parent; 
		while (f != 0)
		{
			start--; 
			if (HT[f].lchild == c) 
				cd[start] = '0'; 
			else
				cd[start] = '1'; 
			c = f;
			f = HT[f].parent; 
		}
		HC[i] = new char[n - start]; 
		strcpy(HC[i], &cd[start]); 
	}
	delete cd; 
}

void HC_OutPut(HuffmanCode HC, int n) 
{
	int length = 0;
	cout << ">> 下面是哈夫曼编码表: " << endl;
	for (int i = 1; i <= n; i++) 
	{
		int j = 0;
		cout << "\t编码" << i << ": ";
		while (HC[i][j] != '\0') 
		{
			cout << HC[i][j++];
			length++;
		}
		cout << endl;
	}
	cout << "\t>> 平均查找长度为: " << (double)length / n << endl;
}

void TransHuffmanCode(HuffmanTree HT,int n, char* cd) 
{
	int start;
	for (int i = 1; i <= 2 * n - 1; i++) 
		if (HT[i].parent == 0)
		{
			start = i;
			break;
		}
	int p = start; 
	cout << "译码后的结果: ";
	while (*cd != '\0') 
	{
		if (HT[p].lchild == 0 && HT[p].rchild == 0)
		{
			cout << HT[p].weight << " "; 
			p = start;
		}
		if (*cd == '0') 
			p = HT[p].lchild;
		else if (*cd == '1') 
			p = HT[p].rchild;
		cd = cd + 1; 
	}
	cout << endl;
}

int main()
{
	HuffmanTree HT; 
	HuffmanCode HC; 
	char cd[MAXSIZE], ch;
	int n; 
	cout << "请输入您生成的哈夫曼树的叶子结点个数: ";
	cin >> n;
	CreateHuffmanTree(HT, n); 
	CreatHuffmanCode(HT, HC, n); 
	HT_OutPut(HT, n); 
	HC_OutPut(HC, n); 
	return 0;
}

